P5504 [JSOI2011]柠檬

可以看出，选出区间的端点大小必须相同，不然可以将一端分在其他区间里，答案不会更劣。

令 $dp_i$ 表示前 $i$ 个贝壳能得到的最大柠檬数， $pos_i$ 表示第 $i$ 个贝壳是第几个这种颜色的贝壳。

那么有转移：

$dp_i=\max\{ dp_{j-1} + s_i(pos_i -pos_j+1)^2\}$

$dp_i=\max\{ dp_{j-1} + s_i{pos_j}^2-2s_ipos_ipos_j-2s_ipos_j\}+ s_i (pos_i+1)^2$

假设两个决策 $j<k$ , 且 $j$ 优于 $k$

$dp_{j-1} + s_i{pos_j}^2-2s_ipos_ipos_j-2s_ipos_j > dp_{k-1} + s_i{pos_k}^2-2s_ipos_ipos_k-2s_ipos_k$

$(dp_{j-1} + s_i{pos_j}^2-2s_ipos_j ) - (dp_{k-1} + s_i{pos_k}^2-2s_ipos_k )> 2s_ipos_i (pos_j-pos_k)$

$\frac{(dp_{j-1} + s_i{pos_j}^2-2s_ipos_j ) - (dp_{k-1} + s_i{pos_k}^2-2s_ipos_k )}{s_i(pos_j-pos_k)}< 2pos_i$

因为最大值在队尾取到，所以用单调栈维护。

#include <cstdio>
#include <vector>
using namespace std;
#define LL long long
#define Lint long long
#define Top Stk[ s[ i ] ][ Stk[ s[ i ] ].size() - 1 ]
#define STop Stk[ s[ i ] ][ Stk[ s[ i ] ].size() - 2 ]

const int MAXN = 100000 , MAXC = 10000;
int n , s[ MAXN + 5 ] , pos[ MAXN + 5 ] , last[ MAXC + 5 ];
vector< int > Stk[ MAXC + 5 ];
LL dp[ MAXN + 5 ];

LL fx( int k , int i ) { return 1ll * s[ k ] * pos[ i ]; }
LL fy( int k , int i ) { return dp[ i - 1 ] + 1ll * s[ k ] * pos[ i ] * pos[ i ] - 2ll * s[ k ] * pos[ i ]; }
LL deltax( int k , int i , int j ) { return fx( k , i ) - fx( k , j ); }
LL deltay( int k , int i , int j ) { return fy( k , i ) - fy( k , j ); }

int main( ) {
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d",&s[ i ]);
		pos[ i ] = pos[ last[ s[ i ] ] ] + 1;
		last[ s[ i ] ] = i;
	}
	
	for( int i = 1 ; i <= n ; i ++ ) {
		for( ; Stk[ s[ i ] ].size() >= 2 && (Lint)deltay( i , STop , Top ) * deltax( i , Top , i ) <= (Lint)deltay( i , Top , i ) * deltax( i , STop , Top ) ; Stk[ s[ i ] ].pop_back() );
		Stk[ s[ i ] ].push_back( i );
		for( ; Stk[ s[ i ] ].size() >= 2 && (Lint)deltay( i , STop , Top ) >= (Lint)2 * pos[ i ] * deltax( i , STop , Top ) ; Stk[ s[ i ] ].pop_back() );
		dp[ i ] = dp[ Top - 1 ] + 1ll * s[ i ] * ( pos[ i ] - pos[ Top ] + 1 ) * ( pos[ i ] - pos[ Top ] + 1 );
	}
	
	printf("%lld\n", dp[ n ] );
	return 0;
}